home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / mac / hypercrd / hc1_2_x / fretext1.sit / Free Text Help_Services v1.01 / card_24224.txt < prev    next >
Text File  |  1990-04-13  |  6KB  |  118 lines
  1. -- card: 24224 from stack: in.01
  2. -- bmap block id: 0
  3. -- flags: 0000
  4. -- background id: 7910
  5. -- name: 
  6.  
  7.  
  8. -- part contents for background part 4
  9. ----- text -----
  10. /* part 2 of 2 */
  11.  
  12.  
  13. EXTENSIONS AND ENHANCEMENTS
  14.  
  15. As mentioned repeatedly above, some significant yet straightforward
  16. extensions to my current free text IR systems are necessary in order to
  17. properly handle 100 MB/day of data. Here, I will briefly sketch out how
  18. I plan to attack the key problems during the coming months.  I assume
  19. that that ample physical storage is available to hold the influx of
  20. information online, in a form which allows access to any item in a
  21. fraction of a second.
  22.  
  23. My systems have to be modified handle multiple text files as a single
  24. database.  I propose to do this by adding a third index file to the
  25. "keys" and "pointers" files -- a "filelist" index file which will simply
  26. contain a list of the database document files along with their lengths.
  27. The structure of the "keys" and "pointers" files will remain unchanged
  28. (which should maximize compatibility with earlier index programs and
  29. minimize the number of new bugs introduced in this step).  The index
  30. building programs will treat each of the documents in the "filelist"
  31. file as part of a single big document for indexing purposes, and the
  32. index browsing programs will consult the "filelist" in order to know
  33. where to go to retrieve lines of context or chunks of full text for
  34. display.
  35.  
  36. A drawback of this multifile "virtual merge" approach is that it will at
  37. times be necessary to open and close files during browsing operations. I
  38. have not yet run tests, and do not know what penalties the operating
  39. system will impose (one hopes only a few milliseconds?) every time a
  40. file is opened and closed.  With the use of modern operating system RAM
  41. caches, I hope that speed will not be a problem.  During typical
  42. browsing operations, I believe that most database references will be
  43. predictable and localized, so caching should help average performance a
  44. lot.
  45.  
  46. Another extension which I plan to implement is to add facilities to
  47. rapidly merge separate index files upon user demand.  Merging
  48. already-sorted index files is a very fast operation which should be
  49. limited only by disk I/O rates.  It will then be possible to keep
  50. indices for each day's (or hour's, or whatever) collection of data
  51. separate until the time at which a user wants to browse a chosen set of
  52. files.  The delay to merge the selected separate indices will be about
  53. equal to the time required for a single sequential scan through the
  54. chosen database.  After that start-up delay, searches will progress at
  55. the normal full speed (sub-second response time for simple queries).
  56. Many data collections which are commonly referred to as a unit can have
  57. their merged index files kept online to avoid any search delays.
  58.  
  59. My current browser programs can already run on one computer while
  60. searching files resident elsewhere on a network.  The generic UNIX
  61. version of my browser can also already be used as a "server" process and
  62. run on one host, sending back only the (relatively) small amounts of
  63. retrieved information that the user wants to see on a local machine.  I
  64. plan to rewrite some parts of my browser programs to make their use as
  65. servers simpler and more efficient; this rewrite will take place along
  66. with the other revisions to introduce new features.
  67.  
  68. Index building itself should not be a computationally infeasible
  69. operation at a 100 MB/day data rate.  My indexer programs already run at
  70. 15-20 MB/hour on a 16 MHz 68030 (Mac IIcx), and I have had reports of 60
  71. MB/hour or better performance on faster machines with more memory and
  72. higher performance disk drives.  I also believe that there is room for a
  73. 20% - 50% speed improvement in my indexing algorithms, by applying some
  74. of the standard quicksort enhancements discussed in many textbooks.  For
  75. storing the index files, a simple and obvious modification that I plan
  76. to make is to give the user complete freedom to put databases and index
  77. files in any directory, on any volume (online storage device) that is
  78. desired.  This will allow archival databases to reside on high-density
  79. optical read-only media, while indices can be built on faster magnetic
  80. media and can be moved to the archive when appropriate.
  81.  
  82. To handle databases larger than about 4 GB (2^32) will require
  83. modifications to my programs, but (assuming that disk space is
  84. available) not major trauma.  If the pointers and counters in the index
  85. data structures are redeclared to be 6 bytes instead of 4 bytes, for
  86. example, it should be possible to handle up to 256 TB of text in theory.
  87. Index file overhead will go up to about 120% instead of the current 80%
  88. of the database text size.  At this point, some simple compression
  89. routines might be worth exploring to increase storage efficiency, if it
  90. can be done without slowing down the retrieval process.
  91.  
  92. Proximity subset searching should still be straightforward to do using
  93. my simple vector representation of the database, but as files get bigger
  94. it may be necessary to hold the large subset vectors on disk and page
  95. them into memory only as needed.  Modern operating systems with large
  96. virtual memory spaces should be able to handle that for the program
  97. automatically.  If I keep the current default 32-byte quantization, then
  98. the subset vectors will still be only 0.4% as big as the total database
  99. text size, and so even in the multigigabyte zone each subset will only
  100. require a few megabytes of space.
  101.  
  102.  
  103. CONCLUSIONS
  104.  
  105. My bottom-line evaluation is that a free-text IR system such as I have
  106. built, plus anticipated extensions, will surely break down -- but not
  107. until reaching file sizes in the 10 GB or larger range, or with
  108. information arriving at a rate greater than 1 GB of text per day.  Then,
  109. problems with data transfer rates and with indexing speed may force one
  110. to find alternative solutions.  Probably a multiprocessor approach using
  111. a partitioned database is the best tactic to take at that point.
  112.  
  113. Meanwhile, I see a lot of value still to be derived from my real-time
  114. high-bandwidth free-text information retrieval tools, particularly as
  115. the costs of data storage continue to decline.
  116.  
  117. /* end of part 2 of 2 */
  118.